#include "AVLTree.h"
#include "BinaryTree.h"
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <cmath>
using namespace std;

AVLTree* avlTreeRoot = NULL;
BinaryTree* biTreeRoot = NULL;
vector<int> dataArray;

void generateRandData (int size)
{
	int i, tmp;
	dataArray.clear();
	srand(time(NULL));
	for (i = 0; i < size; i ++)
	{
		dataArray.push_back(rand()%size);
	}
}

void generateSeqData (int size)
{
	int i;
	dataArray.clear();
	for (i = 0; i < size; i ++)
	{
		dataArray.push_back(i);
	}
}

void insertTestCase ()
{
	int i;
	long s1, e1, s2, e2;
	/*
	s1 = clock();
	for (i = 0; i < dataArray.size(); i ++)
	{
//		printf("insert avl %d of %d\n", i, dataArray.size());
		avlTreeRoot = insert(dataArray[i], avlTreeRoot);
	}
	e1 = clock();
	*/
	s2 = clock();
	for (i = 0; i < dataArray.size(); i ++)
	{
//		printf("insert binary %d of %d\n", i, dataArray.size());
		insert(dataArray[i], biTreeRoot);
	}
	e2 = clock();

	printf("insert test case\nsize: %d\nAVL Tree: %ld ms\nBinary Tree: %ld ms\n\n", 
		dataArray.size(), e1 - s1, e2 - s2);
}

void searchTestCase ()
{
	int i;
	long s1, e1, s2, e2;
	/*
	s1 = clock();
	for (i = 0; i < dataArray.size(); i ++)
	{
		search(dataArray[i], avlTreeRoot);
	}
	e1 = clock();
	destroyTree(avlTreeRoot);
	*/
	s2 = clock();
	for (i = 0; i < dataArray.size(); i ++)
	{
		search(dataArray[i], biTreeRoot);
	}
	e2 = clock();
	destroyTree(biTreeRoot);

	printf("search test case\nsize: %d\nAVL Tree: %ld ms\nBinary Tree: %ld ms\n\n", 
		dataArray.size(), e1 - s1, e2 - s2);
}

void runTestCase ()
{
	insertTestCase();
	searchTestCase();
//	destroyTree(avlTreeRoot);
//	destroyTree(biTreeRoot);
}

void testCase (int size)
{
// 	printf("random test data:\n");
// 	generateRandData(size);
// 	runTestCase();	

	printf("sequential test data:\n");
	generateSeqData(size);
	runTestCase();
}

int main ()
{
//	freopen("avl tree test.txt", "w+", stdout);
	int i;
	for (i = 1000; i <= 1024000; i *= 2)
	{
		testCase(i);
	}
	return 0;
}
